package pri.zjy.dynamicProgramming;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 打家劫舍 III
 * @date 2025/5/28 13:02
 */
public class Rob_337 {

    /**
     * dmsxl:：树形dp-后序
     * <p>
     * 为什么后序？
     * ——递归返回值表示当前节点偷与不偷情况下的最大金额。所以，要根据孩子节点在两种情况下的最大金额，才能决定是否偷当前节点
     */
    public int rob(TreeNode root) {
        if (root == null) return 0;

        int[] ans = robRecursion(root);
        return Math.max(ans[0], ans[1]);
    }

    // 返回值是一个大小为2的一维数组,用于表示当前节点偷与不偷情况下的最大金额, 下标0是不偷,下标1则是偷
    public int[] robRecursion(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        // 左
        int[] left = robRecursion(node.left);
        // 右
        int[] right = robRecursion(node.right);

        // 后序遍历,根据左右孩子判断, 是否偷当前节点
        // 不偷当前节点,则左右都是 可偷可不偷,所以选择金额更大的情况
        int val1 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前节点
        int val2 = node.val + left[0] + right[0];

        return new int[]{val1, val2};
    }

}
